package doublepointer;

import java.util.Collections;
import java.util.List;

/**
 * @Classname : LongestWordInDictionaryThroughDeleting
 * @Description : <a href="https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/">524. 通过删除字母匹配到字典里最长单词</a>
 * @Author : chentianyu
 * @Date 2023/2/23 23:47
 */


public class LongestWordInDictionaryThroughDeleting {
    public String findLongestWord(String s, List<String> dictionary) {
        Collections.sort(dictionary, (String s1, String s2)->{
            if (s1.length() == s2.length()) {
                // 字母顺序
                return s1.compareTo(s2);
            } else {
                // 长度逆序
                return s2.length() - s1.length();
            }
        });

        for (String d : dictionary) {
            int p = 0;
            for (int i=0; i<s.length(); i++) {
                if (s.charAt(i) == d.charAt(p)) {
                    if (++p == d.length()) return d;
                }
            }
        }
        return "";
    }
}
